import { defaultEquals } from '../util.js'
import { Node } from './models/linkedListModels.js'
/**
 * 单向链表
 */
export default class LinkedList {
  constructor(equalsFn = defaultEquals) {
    // 存储链表中的元素数量
    this.count = 0
    // 给元素保存引用
    this.head = undefined
    // 实现一个名为 indexOf 的方法，能够在链表中找到一个特定的元素
    this.equalsFn = equalsFn
  }

  /**
   * 向链表尾部添加一个元素
   * @param {*} element
   */
  push(element) {
    const node = new Node(element)
    let current
    // ECMAScript认为undefined是从null派生出来的，所以把它们定义为相等的
    if (this.head == null) {
      // catches null && undefined
      this.head = node
    } else {
      current = this.head
      // 获取最后一项
      while (current.next != null) {
        current = current.next
      }
      current.next = node
    }
    this.count++
  }

  /**
   * 从链表特定位置移除一个元素
   * @param {number} index
   * @returns
   */
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {
        this.head = current.next
      } else {
        // let previous
        // for (let i = 0; i < index; i++) {
        //   previous = current
        //   current = current.next
        // }
        // // 将 previous 与 current 的下一项链接起来：跳过 current，从而移除它
        // previous.next = current.next
        const previous = this.getElementAt(index - 1)
        current = previous.next
        previous.next = current.next
      }
      this.count--
      return current.element
    }
    return undefined
  }

  /**
   * 循环迭代链表直到目标位置
   * @param {number} index
   * @returns
   */
  getElementAt(index) {
    if (index >= 0 && index < this.count) {
      let node = this.head
      for (let i = 0; i < index && node != null; i++) {
        node = node.next
      }
      return node
    }
    return undefined
  }

  /**
   * 在任意位置插入元素
   * @param {*} element
   * @param {number} index
   */
  insert(element, index) {
    // index <= this.count 中的 = 分析：考虑到可以在末尾插入
    if (index >= 0 && index <= this.count) {
      const node = new Node(element)
      if (index === 0) {
        const current = this.head
        node.next = current
        this.head = node
      } else {
        const previous = this.getElementAt(index - 1)
        const current = previous.next
        node.next = current
        previous.next = node
      }
      this.count++
      return true
    }
    return false
  }

  /**
   * 返回一个元素的位置
   * @param {*} element
   */
  indexOf(element) {
    let current = this.head
    for (let i = 0; i < this.count && current != null; i++) {
      if (this.equalsFn(element, current.element)) {
        return i
      }
      current = current.next
    }
    return -1
  }

  /**
   * 从链表中移除元素
   * @param {*} element
   * @returns
   */
  remove(element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }

  /**
   * 链表长度
   * @returns
   */
  size() {
    return this.count
  }

  /**
   * 链表是否为空
   * @returns
   */
  isEmpty() {
    return this.size() === 0
  }

  /**
   * 获取链表的第一个元素信息
   * @returns
   */
  getHead() {
    return this.head
  }

  /**
   * 清空
   */
  clear() {
    this.head = undefined;
    this.count = 0;
  }

  /**
   * 把链表转化为字符串
   * @returns
   */
  toString() {
    if (this.head == null) {
      return ''
    }
    let objString = `${this.head.element}`
    let current = this.head.next
    for (let i = 1; i < this.size() && current != null; i++) {
      objString = `${objString}, ${current.element}`
      current = current.next
    }
    return objString
  }
}
